1. Technical Field
The present invention relates in general to a method and system for data processing and in particular to a method and system for cache management within a data processing system. Still more particularly, the present invention relates to a method and system for cache management that select an alternative cache entry for replacement in response to a conflict between two cache operation requests.
2. Description of the Related Art
To maximize data processing system performance, the memory in a data processing system is typically arranged hierarchically, with one or more lower levels of memory, which may include nonvolatile storage and a main store, and one or more upper levels of memory, which typically include one or more levels of cache. As will be appreciated by those skilled in the art, cache memory is typically small relative to the main store and affords the processor(s) within the data processing system relatively rapid access to data and instructions.
Cache memories in conventional data processing systems are typically set associative, that is, the main store address of data is utilized to map the data to a particular congruence class that contains multiple entries or members in which the data can be stored. The data (including instructions) stored within the cache are recorded in a cache directory utilizing tags derived from the main store address, typically by selecting predetermined address bits. Thus, in response to receiving a request address, logic within the cache directory compares each of the tags stored in the directory set corresponding to the congruence class to which the request address maps with the tag bits of the request address in order to determine whether or not the requested data resides in the cache. If the requested data resides in the cache, a "hit" occurs and the requested data is handled in accordance with the type of request. On the other hand, if the requested data does not reside in the cache, a "miss" occurs. If a miss occurs in response to a read request, the contents of an entry within the congruence class to which the request address maps must be replaced with the requested data (i.e., castout). Based upon the principle of locality of reference, the entry that is replaced is typically selected in accordance with a least recently used (LRU) algorithm that determines the least recently accessed entry within the congruence class.
In order to maintain data coherency and consistency, multiprocessor data processing systems typically employ either a directory-based or snoop-based communication protocol that notifies cache memories of data accesses occurring elsewhere within the data processing system. The caches utilize the data access information, which hereinafter will be referred to as snoop requests, to invalidate data, writeback data, update the coherency state stored within the directory, or take other appropriate action based upon the coherency protocol implemented within the data processing system.
The present invention includes a recognition that a problem can arise when snoop requests received by a cache collide with cache operation requests received from the cache's associated processor. For example, if a snoop request requires the cache to update a particular directory entry and a read request mapping to the same congruence class as the snoop request misses in the cache, it is possible that the congruence class entry selected for replacement by the replacement algorithm in response to the miss is the same directory entry that must be updated in response to the snoop request. In response to this scenario, conventional caches delay servicing the read request until the update required by the snoop request is performed, thereby creating data latency and decreasing processor performance.
As should thus be apparent, it would be desirable to provide an improved method and system for cache management within a data processing system. In particular, it would be desirable to provide an improved method and system for selecting a cache entry for replacement in response to a collision between cache operation requests.